package com.shangguigu.binarytree;

import lombok.Builder;
import lombok.Getter;
import lombok.Setter;

import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2019/10/17
 * @description: 二叉树测试用
 */
@Getter
@Setter
@Builder
public class BinaryTree {

	private HeroBinaryNode root;

	/**
	 * 先序遍历(递归)
	 * 中-左-右
	 */
	public static void preOrderByRecursive(HeroBinaryNode root) {
		if (root == null) {
			return;
		}
		System.out.printf("%s\t", root.getNo());
		preOrderByRecursive(root.getLeft());
		preOrderByRecursive(root.getRight());
	}

	/**
	 * 先序遍历(迭代)？？
	 * Mine:构造一个栈存放 中 节点，编不下去了...
	 * todo:看来对栈的理解还是不够啊
	 * @param root
	 */
	public static void perOrderByIteration(HeroBinaryNode root) {
		if (root == null) {
			return;
		}
		///栈
		Stack<HeroBinaryNode> stack = new Stack<>();

	}

	/**
	 * 前序遍历查找 no
	 * @param no
	 * @return
	 */
	public static String preOrderSearch(int no, HeroBinaryNode root){
		if (root==null){
			return null;
		}
		if (root.getNo()==no){
			return root.getName();
		}

		String leftName = preOrderSearch(no, root.getLeft());
		if (leftName==null){
			return preOrderSearch(no,root.getRight());
		}
		return null;
	}

	/**
	 * 中序遍历（递归）
	 * 左-中-右
	 *
	 * @param root
	 */
	public static void infixOrderByRecursive(HeroBinaryNode root) {
		if (root == null) {
			return;
		}
		infixOrderByRecursive(root.getLeft());
		System.out.printf("%s\t", root.getNo());
		infixOrderByRecursive(root.getRight());
	}


	//region	删除二叉树节点

	/**
	 * 删除二叉树节点
	 * 思路：删除需要找到前驱节点（类似链表），然后将前驱节点的指向置空
	 * 缺陷：如果返回 void 不能删除 root 节点
	 */
	public static HeroBinaryNode deleteNode(int no, HeroBinaryNode root){
		if (root==null){
			return root;
		}
		if (root.getNo()==no){
			root=null;
			return root;
		}
		if (root.getLeft()!=null &&root.getLeft().getNo()==no){
			root.setLeft(null);
		}
		if (root.getRight()!=null &&root.getRight().getNo()==no){
			root.setRight(null);
		}
		///先序查找并删除
		delete(no,root.getLeft());
		delete(no,root.getRight());
		return root;
	}

	/**
	 * TODO:这里将root置为空是没有用的！因为进入这个方法后，传入的是这个引用的地址，而在方法中置空只是将改变了局部变量的地址，而对于原来的地址仍然是存在的！解决方案即上面
	 * @param no
	 * @param root
	 */
	public static void delete(int no, HeroBinaryNode root){
		if (root==null){
			return ;
		}
		if (root.getNo()==no){
			root=null;
			return ;
		}
		if (root.getLeft()!=null &&root.getLeft().getNo()==no){
			root.setLeft(null);
		}
		if (root.getRight()!=null &&root.getRight().getNo()==no){
			root.setRight(null);
		}
	}
	//endregion

}
